// https://leetcode.cn/problems/smallest-integer-divisible-by-k/description/?envType=daily-question&envId=2025-11-25

// 算法思路总结：
// 1. 模拟由1组成的数字对k取模的过程
// 2. 使用哈希表检测余数循环，避免无限循环
// 3. 余数为0时返回当前数字长度，出现循环返回-1
// 4. 时间复杂度：O(K)，空间复杂度：O(K)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_set>

class Solution 
{
public:
    int smallestRepunitDivByK(int k) 
    {
        int resid = 1 % k;

        unordered_set<int> vis;
        while (resid && vis.insert(resid).second)
        {
            resid = (10 * resid + 1) % k;
        }

        return resid ? -1 : vis.size() + 1;
    }
};

int main()
{
    int k1 = 1, k2 = 3;
    Solution sol;

    cout << sol.smallestRepunitDivByK(k1) << endl;
    cout << sol.smallestRepunitDivByK(k2) << endl;

    return 0;
}